package com.xxy.stack;
import java.sql.Statement;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
/**
 * @author xxy
 * @create 2020 11 08 19:17
 * =======后缀表达式计算的实现==========
 * 从左往右扫描表达式，遇到数字时，将其入栈，遇到运算符事，弹出栈顶的两个数，用运算符对他们进行相应的计算，并将结果入栈：
 * 重复上述过程直到表达式最右端，最后运算处理的值即为表达式的结果。
 * =============中缀表达式转后缀表达式=================
 * 1.初始化两个栈，运算符栈s1和存储中间结果的栈s2;
 * 2.从左往右扫描两个中缀表达式
 * 3.遇到操作数时，将其压入栈s2
 * 4.遇到运算符时，比较与s1栈顶元素运算符的优先级
 * 4.1如果s1为空，或栈顶运算符为“（”，则直接入栈
 * 4.2否则，若优先级比栈顶运算符的高，也将其压入栈
 * 4.3否则，将s1栈顶的元素压入栈s2中，再次转到4.1与s1中新的栈顶运算符相比较
 * 5.遇到括号时：
 * 5.1如果是（，则直接压入栈s1
 * 5.2如果是），则依次弹出s1栈顶的运算符，并压入栈s2,直到遇到）为止，此时将这一对括号丢掉
 * 6.重复步骤2到5.直到表达式的最右边
 * 7.将s1中剩余的运算符依次弹出并压入栈s2.
 * 8依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
 */
public class PolandNotation {
    public static void main(String[] args) {
        //先定义逆波兰表达式
        //(3+3)*5-6=》3 4 + 5 * 6 - ;
        //将suffixexpression放到ArrayList中
        //将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算

        String suffixExpression = "30 4 + 5 * 6 - ";
        int result =calculate(getListString(suffixExpression));
        System.out.println("结果为："+result);
        //================
        String expression="1+((2+3)*4)-5";
       List<String> infix=toInfixExpressionList(expression);
        System.out.println("中缀"+infix);
        List<String> suffix =pareSuffixExpressionList(infix);
        System.out.println("后缀"+suffix);
        int num =calculate(suffix);
        System.out.println("结果为"+num);

    }
    public static List<String> getListString(String suffixExpression) {
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    /**
     * 先将中中缀表达式转成对应的数组
     * @param
     * @return 返回对应的数组
     */
    public static List<String> toInfixExpressionList(String s){
        List<String> list = new ArrayList<>();
        int i=0;
        String str;//对对位数进行拼接
        char c;
        do{
            //如果是非数字
            if((c=s.charAt(i))<48||(c=s.charAt(i))> 57){
                list.add(""+c);
                i++;
            }else{//如果是一个数
                str="";
                while(i<s.length()&&(c=s.charAt(i))>=48&&(c=s.charAt(i))<=57){
                    str+=c;
                    i++;//拼接
                }
                list.add(str);
            }
        }while(i<s.length());
        return list;
    }
    //将中缀表达式转成后缀表达式的方法
    public static List<String> pareSuffixExpressionList(List<String> li){
        Stack<String> s1 = new Stack<>();//符号栈
        List<String> s2 = new ArrayList<>();
        for(String item:li){
            if(item.matches("\\d+")){
                s2.add(item);
            }else if(item.equals("(")){
                s1.push(item);
            }else if(item.equals(")")){
                while(!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                s1.pop();
            }else {
                while(s1.size()!=0&&Operation.getValue(s1.peek())>= Operation.getValue(item)){
                    s2.add(s1.pop());
                }
                s1.push(item);
            }
        }
        while (s1.size()!=0){
            s2.add(s1.pop());
        }
        return s2;
    }

    /**
     *  //计算方法
     * @param ls
     * @return 返回为计算结果
     */
    public static int calculate(List<String> ls) {
        Stack<String> stack = new Stack<String>();
        for (String str : ls) {
            if (str.matches("\\d+")) {
                stack.push(str);
            }else{
                int num2 =Integer.parseInt(stack.pop());
                int num1 =Integer.parseInt(stack.pop());
                int res =0;
                switch (str){
                    case "+":
                        res =num2+num1;
                        break;
                    case "-":
                        res =num1-num2;
                        break;
                    case "*":
                        res =num1*num2;
                        break;
                    case "/":
                        res=num1/num2;
                        break;
                    default:
                        break;
                }
                stack.push(res+"");
            }
        }
        return Integer.parseInt(stack.pop());
    }
}
//计算优先等级
class Operation{
    private static int ADD=1;
    private static int SUB=1;
    private static int MUL =2;
    private static int DIV =2;
    //返回优先等级
    public static int getValue(String operation){
        int result =0;
        switch(operation){
            case "+":
                result =ADD;
                break;
            case "-":
                result =SUB;
                break;
            case "*":
                result =MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                break;
        }
        return result;
    }
}